package org.hot100_1;

import java.util.Arrays;

public class leetcode79 {
//    public int numSquares(int n) {
//
//        int [] dp =new int[n+1];
//
//        for (int i = 0; i <dp.length; i++) {
//            dp[i]=Integer.MAX_VALUE;
//        }
//        dp[0]=0;
//
//        //先遍历背包，再遍历物品。背包为0-n，物品为从1开始的数字。
//        for (int i = 1; i <=n; i++) {
//            for (int j = 1; j*j<=i; j++) {
//                //Math.min(dp[i],dp[i-j*j]+1)中的dp[i]可以理解为：之前的填充背包时，没有涉及到当前的数字，所能够组成的最少数量。没有选择新加入的数字。
//                //而dp[i-j*j]+1可以理解为选择了新加入的数，所以要+1，需要找到剩下的容量(i-j*j)的最少数量.
//                dp[i]=Math.min(dp[i],dp[i-j*j]+1);
//            }
//        }
//
//        return dp[n];
//    }

    public int numSquares(int n) {
        int [] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        dp[1]=1;

        for (int i = 1; i <=n; i++) {
            for (int j = 1; j * j<=i; j++) {
                dp[i]=Math.min(dp[i],dp[i-j*j]+1);
            }
        }

        return dp[n];
    }
}
